/* Soot - a Java Optimization Framework
 * Copyright (C) 2005 Antoine Mine
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

/**
 * Implementation of the paper "A Combined Pointer and Purity Analysis for
 * Java Programs" by Alexandru Salcianu and Martin Rinard, within the
 * Soot Optimization Framework.
 *
 * by Antoine Mine, 2005/01/24
 */

/**
 * Refined to build a FiltedCallGraph for filting out some unwanted methods with generic types
 * 
 * by Wei He, 2010/02/09
 */

package mmpathgen.callgraphanalysis;

import java.util.*;

import soot.*;
import soot.util.*;
import soot.jimple.toolkits.annotation.purity.SootMethodFilter;
import soot.jimple.toolkits.callgraph.*;
import soot.toolkits.graph.*;

/**
 * Builds a DirectedGraph from a CallGraph and SootMethodFilter.
 * 
 * This is used in AbstractInterproceduralAnalysis to construct a reverse pseudo
 * topological order on which to iterate. You can specify a SootMethodFilter to
 * trim the graph by cutting call edges strarting
 * 
 * Methods filtered-out by the SootMethodFilter will not appear in the
 * FiltedGraph!
 */
public class BoundedCallGraph implements DirectedGraph<SootMethod> {

	protected Set<SootMethod> nodes;
	protected Map<SootMethod, List<SootMethod>> succ;
	protected Map<SootMethod, List<SootMethod>> pred;
	protected List<SootMethod> heads;
	protected List<SootMethod> tails;
	protected int size;

	/**
	 * The constructor does all the work here. After constructed, you can safely
	 * use all interface methods. Moreover, these methods should perform very
	 * fastly...
	 * 
	 * The FiltedGraph will only contain methods in call paths from a method in
	 * head and comprising only methods wanted by filter. Moreover, only
	 * concrete methods are put in the graph...
	 * 
	 * @param heads
	 *            is a List of SootMethod
	 */
	@SuppressWarnings("unchecked")
	public BoundedCallGraph(CallGraph cg, Iterator<SootMethod> heads, int mtdBound) {
		// filter heads by filter
		List<SootMethod> filteredHeads = new LinkedList<SootMethod>();
		while (heads.hasNext()) {
			SootMethod m = (SootMethod) heads.next();
			if (m.isConcrete())
				filteredHeads.add(m);
		}

		this.nodes = new HashSet(filteredHeads);

		MultiMap s = new HashMultiMap();
		MultiMap p = new HashMultiMap();

		// simple breadth-first visit
		Set<SootMethod> remain = new HashSet<SootMethod>(filteredHeads);
		int nb = 0;
		while (!remain.isEmpty()) {
			Set newRemain = new HashSet();
			Iterator it = remain.iterator();
			while (it.hasNext() && nb < mtdBound) {
				SootMethod m = (SootMethod) it.next();
				Iterator itt = cg.edgesOutOf(m);
				while (itt.hasNext()) {
					Edge edge = (Edge) itt.next();
					SootMethod mm = edge.tgt();
					if (mm.isConcrete()) {
						if (this.nodes.add(mm))
							newRemain.add(mm);
						s.put(m, mm);
						p.put(mm, m);
					}
				}
				nb++;
			}
			remain = newRemain;
		}
		G.v().out.println("[AM] number of methods to be analysed: " + nb);

		// MultiMap -> Map of List
		this.succ = new HashMap();
		this.pred = new HashMap();
		this.tails = new LinkedList();
		this.heads = new LinkedList();
		Iterator<SootMethod> it = this.nodes.iterator();
		while (it.hasNext()) {
			SootMethod x = it.next();
			Set ss = s.get(x);
			Set pp = p.get(x);
			this.succ.put(x, new LinkedList(ss));
			this.pred.put(x, new LinkedList(pp));
			if (ss.isEmpty())
				this.tails.add(x);
			if (pp.isEmpty())
				this.heads.add(x);
		}

		this.size = this.nodes.size();
	}

	/** You get a List of SootMethod. */
	public List<SootMethod> getHeads() {
		return heads;
	}

	/** You get a List of SootMethod. */
	public List<SootMethod> getTails() {
		return tails;
	}
	
	/** You get a Set of SootMethod. */
	public Set<SootMethod> getNodes() {
		return nodes;
	}

	/** You get an Iterator on SootMethod. */
	public Iterator<SootMethod> iterator() {
		return nodes.iterator();
	}

	public int size() {
		return size;
	}

	/** You get a List of SootMethod. */
	public List<SootMethod> getSuccsOf(SootMethod s) {
		return succ.get(s);
	}

	/** You get a List of SootMethod. */
	public List<SootMethod> getPredsOf(SootMethod s) {
		return pred.get(s);
	}
}
